1. Field of the Invention
The present invention relates generally to colorimetry, more particularly to nonlinear tristimulus color data storage, retrieval and interpolation, and, more specifically to memory mapping and data interpolation strategy for 24-bit L*H*C* to 24-bit RGB space data.
2. Description of Related Art
Colorimetry has long been recognized as a complex science. Essentially, as defined in 1931 by the Commission Internationale L'Eclairage (CIE), three primary colors (X, Y, Z) can be combined to define all light sensations we experience with our eyes; that is, the color matching properties of an ideal trichromatic observer defined by specifying three independent functions of wavelength that are identified with the ideal observer's color matching functions form an international standard for specifying color. In general, it has been found possible and convenient to represent color stimuli vectors by a three-dimensional spatial construct, called a tristimulus space or a color space. The fundamentals of such three-dimensional constructs are discussed in the literature, such as Principles of Color Technology, by Billmeyer and Saltzman, published by John Wiley & Sons, Inc., NY, copyright 1981 (2d. ed.) and Color Science: Concepts and Methods, Quantitative Data and Formulae, by Wyszecki and Stiles, published by John Wiley & Sons, Inc., copyright 1982 (2d ed.), see e.g., pages 119-130.
A variety of trichromatic model systems provide alternatives for both the hardware and software system designers--e.g., the red, green, blue (RGB) model commonly used in computer video displays; the cyan, magenta, yellow (and black) (CMY(K)) model used extensively in color hard copy apparatus; the hue, saturation, value (HSV) model; the hue, lightness, saturation (HLS) model; the luminance, red-yellow scale, green-blue scale (L*a*b*) model; the YIQ model used in commercial color television broadcasting; and others. Such works as Fundamentals of Interactive Computer Graphics, by Foley and Van Dam, Addison-Wesley Publishing Company, see e.g., pages 606-621, describe a variety of tri-variable color models.
Color input and output devices--such a scanners, cathode ray tube (CRT) video monitors, and printers--present color images in a device-dependent fashion. For example, CRT guns are driven by RGB values (voltage levels or other input signal functions, referred to hereinafter as data triplets or color coordinates) that are stored in a frame buffer. Those RGB values index over the color space of each particular model video monitor; in other words, the color produced by a CRT on a pixel of its screen for a given RGB triplet of values is unique to that device. Because of device design dependency, the same RGB triplet may produce a very different color or hue when displayed on a different model CRT and still a different color in a hard copy made with a color printer.
Color transformation (also referred to in the art as color correction and cross-rendering) between model systems in digital data processing presents many problems to the original equipment manufacturer. The transformation of data from one device to another device is difficult because the color matching relationship between those systems are generally non-linear. Therefore, a crucial problem is the maintaining of color integrity between an original image from an input device (such as a color scanner, CRT monitor, digital camera, computer software/firmware generation, and the like) and a translated copy at an output device (such as a CRT monitor, color laser printer, color inkjet printer, and the like). A transformation from one color space to another requires complex, non-linear computations in multiple dimensions. Since such is not describable mathematically, it is known to use very large look-up tables to approximate a transformation between trichromatic model systems to correlate the wide spectrum of color hues that exist. A lookup table of input versus output data can be generated for any set of devices. There are a variety of methods for building a device-dependent look-up table for a particular device. The 1975 U.S. Pat. No. 3,893,166 to Pugsley provides an example. However, semiconductor memory is relatively expensive and other data storage technologies for maintaining such tables--disks, tape, and the like--are too slow.
Bytes of data correlated in three dimensions can be represented as a construct, such as a polyhedral lattice, with each corner of a cube representing a data point, that is, a data set having coordinate values in each of the planes is stored in a memory location, or node, as a look-up table. Note that in this art, the term node may seem to have multiple meanings because of the nature of multidimensional spatial constructs that are used in such systems; (1) it can refer to the coordinates of the space of an input pixel; (2) it can refer to stored data points between which interpolation of data may occur; (3) when a color data map of multi-dimensional color space is stored in a two-dimensional computer memory, it can refer to the memory address itself which has a one-to-one correspondence with the incoming pixel coordinates; (4) it can refer to the data stored at each memory location that represents the output pixel data which itself can refer to the coordinates of a second spatial point. The exact meaning of the term both in the art and in this specification thus often must be taken from the context in which it is used.! The total look-up table is made of many such cubes as shown in FIG. 1 for an RGB color space construct. However, to store a typical printer color transformation data point value for every monitor RGB value in a look-up table would require fifty megabytes or more of random access memory which is cost prohibitive in the state-of-the-art. Thus, it is economic to store only a limited number of data points and to use interpolation methods to derive intermediate data points within the lattice. In making the transform from one tristimulus system to another, trilinear or quadrilinear interpolation methods have been used. However, with non-linear data, true interpolation is time consuming and impractical when dealing with, for example, a print image comprising millions of pixels. Therefore, there are a variety of data storage and interpolation methods proposed in the art. The use of limited data for interpolation is described in U.S. Pat. No. 4,477,833 to Clark et al. A method of variable spacing of selected non-linear data and storing data in accordance with regard to the particular color curve is described by Morton in U.S. Pat. No. 5,321,797. An improved interpolation approximation by a lattice subdivision technique is taught by Gondek in U.S. patent application Ser. No. 08/504,406 (assigned to the common assignee of the present invention).
Transforming input data triplets into printer RGB (or CMY, or CMYK) values also can be accomplished by utilizing color measurement tools and device-independent color spaces. Device-independent color provides accurate color matching based on an absolute color standard, such as the CIE. A device-independent color space provides a way for describing the appearance of a color without referring to the mechanism that produced the color. For example:
first, a function is constructed that transforms RGB data points from the color space of a monitor (that is, the table of input-output correlations) into a device-independent color space, e.g., the CIE L*a*b* color space;
second, a function is constructed that transforms color data points from the device-independent color space, the CIE L*a*b* color space, into the color space of a particular printer; and
using these two functions, the monitor RGB data values can be transformed to L*a*b* data triplets and the L*a*b* data triplets transformed into the printer data triplets, thus providing printer output that matches the original input image colors as viewed on the CRT monitor.
However, in addition to the data storage and access problems referred to above, the mapping of the monitor RGB values into printer RGB values is time intensive to perform on each and every colored pixel in an image before completely printing that image. Therefore, it is economic to pre-compute and store the output data triplets for a subset of input values and then to use a fast interpolation algorithm to approximate the transform function for intermediate output data values, i.e., those that have not been pre-computed and stored.
It is sometimes desirable to identify components of color differences in terms of correlates of chroma (relative colorfulness, saturation, e.g., a strong or weak brightness) and hue (color, as measured by wavelength). One specific tristimulus space construct, L*H*C*, uses luminance (directional intensity; reflectance or transmittance; "Y" in the CIE standard tristimulus coordinate system), hue, and chroma, generally referred to as simply "LHC," is cylindrical as shown in FIGS. 2A and 2B, where FIG. 2B depicts a hue-chroma plane of constant luminance, hue changing along circles of constant chroma. The entire color map consists of these planes stacked on top of each other.
A scanner produces device-dependent RGB data. It is desirable for an end user to be able to have output print control, but the output data will also be in RGB or CMYK data, also device-dependent. Data control, and hence output control, can be provided in a color space only where there is independence of the variables (e.g., in RGB, adjusting R would affect any color hue that has a red component, not just red, and both luminance and chroma; similarly with L*a*b* attempted control). Thus, control can only be done in a color space that will not create shifts in other variables. Luminance, L*, hue, H*, and chroma, C* are independent variables. Therefore, it is advantageous to transform RGB input data through a LHC construct because any of the variables can be adjusted independently and thus are readily adaptable to end-user hardware and software preference controls.
To provide a memory having each and every output value available in a transformation from a 24-bit LHC coordinate system (i.e., three 8-bit words) to a 24-bit RGB coordinate system again would require a very large memory to contain a look-up table to correlate the wide spectrum of color hues available. This solution is commercially impractical.
Thus, there is a need for an efficient mechanism for the nonlinear tristimulus color data storage, retrieval and interpolation when converting from a cylindrical LHC color space construct to a rectangular RGB color space construct.
There is also a need for a fast and economical method for storing and fetching limited points of an output data table and interpolating the stored data to obtain a proper transform between multi-variable data processing systems.
There is a need for an improved process that transforms the color values from one particular device color space into the color space of another device in a fast, economical manner.